import java.util.Stack;

/**
 * @author 03010570
 * @date 2020/06/30
 * describe:    LeetCode: 剑指 Offer 52 两个链表的第一个公共节点 https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
 * <p>
 * 第一种想法： 使用两个栈，把两个链表全部加进去，从后往前进行比较，最后一个相等的节点即为第一个公共节点
 * 时间复杂度 ： O(M+N)   两个链表的长度
 * 空间复杂度 ：O(M+N)    两个栈的额外空间
 * <p>
 * 第二种想法： 两个链表遍历一遍，计算两个链表的长度，比较最后一个 节点是否相等，不相等说明没有公共节点，计算长度差。
 * 较长的链表先走 长度差，再两个链表同时往后走，第一个相等的节点即为第一个公共节点。
 * 时间复杂度 ： O(M+N)
 * 空间复杂度 ： O(1)
 */
public class LeetCode_sword_offer_52 {

    public static void main(String[] args) {

    }

    /**
     * * 第二种想法： 两个链表遍历一遍，计算两个链表的长度，比较最后一个 节点是否相等，不相等说明没有公共节点，计算长度差。
     * * 较长的链表先走 长度差，再两个链表同时往后走，第一个相等的节点即为第一个公共节点。
     * * 时间复杂度 ： O(M+N)
     * * 空间复杂度 ： O(1)
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lengthA = getLength(headA);
        int lengthB = getLength(headB);
        ListNode nodeA = headA;
        ListNode nodeB = headB;
        int diff = lengthA - lengthB;
        if (diff > 0) {
            for (int i = 0; i < diff; i++) {
                nodeA = nodeA.next;
            }
        } else {
            for (int i = 0; i > diff; i--) {
                nodeB = nodeB.next;
            }
        }
        while (nodeA != nodeB) {
            nodeA = nodeA.next;
            nodeB = nodeB.next;
        }
        return nodeA;
    }

    private static int getLength(ListNode node) {
        int length = 0;
        ListNode temp = node;
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        return length;
    }

    /**
     * * 第一种想法： 使用两个栈，把两个链表全部加进去，从后往前进行比较，最后一个相等的节点即为第一个公共节点
     * * 时间复杂度 ： O(M+N)   两个链表的长度
     * * 空间复杂度 ：O(M+N)    两个栈的额外空间
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        Stack<ListNode> stackA = new Stack<>();
        Stack<ListNode> stackB = new Stack<>();
        ListNode preA = headA;
        ListNode preB = headB;
        while (preA != null) {
            stackA.push(preA);
            preA = preA.next;
        }
        while (preB != null) {
            stackB.push(preB);
            preB = preB.next;
        }
        if (stackA.isEmpty() || stackB.isEmpty() || stackB.peek() != stackA.peek()) {
            return null;
        }
        while (!stackA.isEmpty() && !stackB.isEmpty()) {
            preA = stackA.pop();
            preB = stackB.pop();
            if ((stackA.isEmpty() && stackB.isEmpty()) || stackA.peek() != stackB.peek()) {
                return preA;
            }
        }
        return null;
    }

}
